package main.leetcode.offer.secondround.from03to50;

/** 14-I.减绳子 */
public class ex14I {
    public static void main(String[] args) {
        System.out.println(new ex14I().cuttingRope(8));
        System.out.println(new ex14I().cuttingRope(2));
        System.out.println(new ex14I().cuttingRope(10));
    }
    /** 暴力递归，记忆集优化 */
    public int cuttingRope1(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 1;
        }
        int[] memo = new int[n + 1];
        memo[0] = 0;
        memo[1] = 1;
        memo[3] = 2;
        return memorize(memo, n);
    }

    private int memorize(int[] memo, int n) {
        if (memo[n] > 0) {
            return memo[n];
        }
        int res = 0;
        for (int i = 1; i < n; ++i) {
            res = Math.max(res, Math.max(i * (n - i), i * memorize(memo, n - i)));
        }
        return res;
    }

    /** 贪心 */
    public int cuttingRope(int n) {
        if (n == 2) {
            return 1;
        }
        if (n == 3) {
            return 2;
        }

        int res = 1;
        while (n > 4) {
            res *= 3;
            n -= 3;
        }
        return res * n;
    }
}
